package history

import "fmt"

func heapSort() {

}

/**
 * @Description: 约瑟夫环问题
 * @Keyword: 1.数组 2.链表 3.递归
 * @Author: kami
 * @Date: 2022/8/8 17:21
 **/
func josephus_problem(nums []int, m int) {

	//josephus_slice(nums, m)
	josephus_linkNode(nums, m)
}

func josephus_slice(nums []int, m int) {
	var remove = make([]bool, len(nums))
	var cnt int
	var k int
	var idx int
	for cnt != len(nums) {
		if idx == len(nums) {
			idx = 0
		}
		if !remove[idx] {
			k++
			if k == m {
				cnt++
				fmt.Printf("第 %d 个弹出的数字是 %d", cnt, nums[idx])
				fmt.Println()
				remove[idx] = true
				k = 0
			}
		}
		idx++
	}
}

type node struct {
	idx  int
	pre  *node
	next *node
}

func josephus_linkNode(nums []int, m int) {
	var head = &node{
		idx: 0,
	}
	var pre = head
	for i := 1; i < len(nums); i++ {
		var cur = &node{
			idx: i,
		}
		cur.pre = pre
		pre.next = cur
		pre = cur
	}
	head.pre = pre
	pre.next = head

	var curNode = head
	var cnt int
	for curNode != curNode.next {
		var k = 1
		for k < m {
			curNode = curNode.next
			k++
		}
		cnt++
		fmt.Printf("第 %d 个弹出的数字是 %d", cnt, nums[curNode.idx])
		fmt.Println()
		curNode.pre.next = curNode.next
		curNode.next.pre = curNode.pre
		curNode = curNode.next
	}
	cnt++
	fmt.Printf("第 %d 个弹出的数字是 %d", cnt, nums[curNode.idx])
	fmt.Println()
}

// f(N,M)=(f(N−1,M)+M)%N
func josephus_dfs(n, m int) {
	var p = 0
	for i := 2; i <= n; i++ {
		p = (p + m) % i
		fmt.Println(p + 1)
	}
	return
}
